$\mathtt{Update\ 2019.11.08}$

题面

在字符串 $A$ 中，如果字符串 $B$ 是 $A$ 的子串，那么就删除在 $A$ 中第一个出现的 $B$，然后拼接在一起，一直重复上述步骤直到 $B$ 不再是 $A$ 的子串

|A|$\le 10^6$

解题思路

KMP+栈

分析

1、字符串匹配的问题，想到 $KMP$

2、在匹配过程中，如果匹配成功了，就将子串 $B$ 删除，可以证明，对之前不会产生影响

3、删了再加入，类似栈的操作，因此用栈维护上述操作过程中的字串即可

过程

1、$KMP$ 板子跑一遍

2、在 $KMP$ 过程中，把遍历到的 $i$（不是字符，而是下标）入栈，当匹配上 $B$ 时，就把匹配的部分出栈，然后 $j$ 从栈顶的 $i$ 所能匹配到的最大的位置开始（就是 f[i] 记录的值），继续做 $KMP$

时间复杂度：$B$ 自身匹配一次 $+A$ 与 $B$ 匹配一次$+A$ 中最多每个字符进出栈一次，为 $O(|A|)$

Code

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int la,lb,res;
char a[N],b[N];
int p[N],f[N];//分别表示B串自身匹配的结果、A串与B串匹配的结果
int St[N],top;
int main()
{
    int i,j;
    scanf("%s",a+1);
    scanf("%s",b+1);
    la=strlen(a+1);
    lb=strlen(b+1);
    for(i=2,j=0;i<=lb;i++) {//自身匹配
        while(j&&b[i]!=b[j+1])
            j=p[j];
        if(b[i]==b[j+1])
            j++;
        p[i]=j;
    }
    for(i=1,j=0;i<=la;i++) {//A与B匹配
        while(j&&a[i]!=b[j+1])
            j=p[j];
        if(a[i]==b[j+1])
            j++;
        f[i]=j;//记录结果
        St[++top]=i;//入栈
        if(j==lb)//如果匹配成功，弹出，并更新j值
            top-=lb,j=f[St[top]];
    }
    for(i=1;i<=top;i++)//大功率输出
        printf("%c",a[St[i]]);
    return 0;
}

再扔道题 Luogu P3121 [USACO15FEB]审查（黄金）Censoring (Gold)

devil.